package com.qfedu.entity.course12;

import java.util.Arrays;

public class MergeSort {
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        //计算中间位置
        int mid = arr.length / 2;
        //分解为左右两部分,分别排序
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        left = mergeSort(left);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        right = mergeSort(right);
        //合并两个排序后的数组为一个数组
        return merge(left, right);
    }

    private static int[] merge(int[] l, int[] r) {
        int[] result = new int[l.length + r.length];
        int lIndex = 0;
        int rIndex = 0;
        for (int i = 0; i < result.length; i++) {
            if (lIndex < l.length && rIndex < r.length) {
                if (l[lIndex] <= r[rIndex]) {
                    result[i] = l[lIndex++];
                } else {
                    result[i] = r[rIndex++];
                }
            } else if (lIndex >= l.length) {
                result[i] = r[rIndex++];
            } else {
                result[i] = l[lIndex++];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] integers = new int[]{6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        System.out.println(Arrays.toString(mergeSort(integers)));
    }
}
